In~\cite{lonati2011towards} V. Lonati and M. Pradella wanted to create a new
model that combines the automata idea of states and the Wang tile idea of
coloring edges. They also wanted to improve the expressive power in the way
that the class of languages of this model is in REC. The first idea of
adding expressive power to the model of Section~\ref{scan_drec} was to combine
it with a 4DFA. The next automata model can change the color of a Wang tile
depending on the current state. This model is called 2D free deterministic
automaton and was introduced in~\cite{lonati2011towards}.
\begin{definition}
A \emph{2D free deterministic automaton} is a 7-tuple \\
$M = (Q, \Sigma, C, \delta, q_0, q_e, q_r)$, where
\begin{compactitem}
  	\item $Q$ is a finite set of states, 
	\item $\Sigma$ is a finite input alphabet,
	\item $C$ is a finite set of colors,
	\item $\delta: \Sigma_C \times (Q \backslash q_e, q_r\}) \rightarrow \Sigma_C
	\times Q \times Dirs$ is a partial function such that $(A',
	q', d) \in \delta(A, q)$ implies $A'$ extends $A$ and
	\item $q_0, q_e, q_r$ are the initial, accepting and rejecting states
\end{compactitem}
\end{definition}
At first let us regard an example. Therefore in Section~\ref{urec} we defined
the language $L_{fr = r'}$ which is the language of all pictures that have a row
which is equal to the first row. This language can be recognized by a 2D free
automaton $M$.
\begin{example}
$M = (Q, \Sigma, C, \delta, q_0, q_e, q_r)$, where
\begin{compactitem}
\item $Q = \{q_0, q_e, q_r\} \cup \Sigma \cup \bar {\Sigma}$% $\cup
% \Sigma_{last} \cup \bar {\Sigma}_{last}$
, where symbols in $\bar{\Sigma}$ are barred versions of symbols in $\Sigma$,
and they are used to distinguish the part of the computation when the head moves
leftwards.
% Symbols in $\Sigma_{last}$ are with
% index $last$ marked versions of symbols in $\Sigma$, and will be used to
% distinguish the last symbol in the first row. Symbols in $\Sigma_{last}$ are
% barred versions of the symbols in $\Sigma_{last}$, and they are used like the
% symbols in $\bar{\Sigma}$ to distinguish the part of the computation when the
% head moves leftwards only for the last symbol of the first row.
\item $\Sigma = \{a, b\}$ is the input alphabet,
\item $C = \{\times, \circ\}$ is the set of colors, where $\times$ is the reject
color, when it finds out that a row is different from the first one, and $\circ$
shall be used to mark the edges of the position while it is visited the first
time.
\item The transition function $\delta$ is similar to the one that can be found
 in~\cite{lonati2011towards}. 
% It is not the same because we added four more
% states to the automaton $M$. Furthermore is our states Namensgebung a little bit
% different to the one in ~\cite{LonatiPradella2011}. These four states are used
% to distinguish if a picture is not in $L_{fr = r'}$. A picture $p$ for example
% where $p(1, 1) \neq p(1, i)$ for all $2 \leq i \leq l_2(p)$ can now be rejected.
% For this the automaton $M$ works with this new four states similar to the states
% that are in $\Sigma$ and $\bar{\Sigma}$. The only difference is when $M$ reads
% in a state $\tau \in \Sigma_{last}$ the tile
% \begin{tabular}{E{0.34cm}E{0.5cm}E{0.34cm}}
%  & $\circ$ & \tabularnewline 
% $\circ$ & \boxed{\sigma} & $\times$ \tabularnewline
%  & \# &   
% \end{tabular} or \begin{tabular}{E{0.34cm}E{0.5cm}E{0.34cm}}
%  & & \tabularnewline
% $\circ$ & \boxed{\sigma} & $\times$ \tabularnewline
%  & \# &   
% \end{tabular} with $\sigma \in \Sigma$ and the unindexed version of $\tau$ is
% not equal to $\sigma$ then $M$ changes to state $z_r$. If $M$ read the tile
% \begin{tabular}{E{0.34cm}E{0.5cm}E{0.34cm}}
%  & \# & \tabularnewline 
% $\circ$ & \boxed{\sigma} & \# \tabularnewline 
%  & & 
% \end{tabular} in state $z_0$, $M$ marked the tile as visited moves one field
% left and changes to the state $\tau \in \Sigma_{last}$ where $\tau$ is the with
% index $last$ marked version of the symbol $\sigma$.
\end{compactitem}
\end{example}
The automaton $M$ starts in the upper left corner and reads the first symbol.
After this, it changes to the state that has the same name like the symbol on the
first position. Now the automaton checks row by row and looks if the first
symbol in the row is equal to the state name. If it is equal, $M$ marks the
tiling as visited and checks the other rows. If the symbol was not equal to the
state the automaton $M$ colors the right position of the Wang tile as rejected
and also checks the next rows. This will be proceeded until $M$ reaches the
bottom border. After this, $M$ changes its state to $q_0$ and checks the second
symbol in the first row. Again the automaton checks row-wise. Therefore it moves
first to the upper left corner and walks down. Now $M$ checks only those rows
that are colored as visited. Is a row marked as visited, $M$ moves in this row
from left to right until it finds an unmarked tile or a tile that is marked as
rejected. If it finds an unmarked tile, $M$ compares the current symbol with
the current state, marks the current tile and scans the rest of the picture. If
$M$ reads the right border symbol it accepts the picture if the symbol on this
position is equal to the current state. If it reaches the corner on the bottom
right and the symbol is not equal to the current state, it rejects the picture.
After $M$ has made a decision about the coloring of a tile in the picture, $M$
changes to an extra state that is corresponding to one symbol in $\Sigma$. This
state is used to walk to the left border. After reaching the left border, $M$
changes back to the previous state. $M$ also rejects the input picture $p$,
if it reaches the upper right corner of $p$ twice.

For a better vizualisation, you find an accepted input picture and the
partial Wang picture obtained by the computation next. All symbols which have never been
read are omitted by the automaton.
\begin{center}
\begin{tabular}{|E{0.22cm}|E{0.22cm}|E{0.22cm}|E{0.22cm}|E{0.22cm}|}
\hline
a & b & a & a & b \tabularnewline
\hline
b & a & b & a & a \tabularnewline
\hline
a & a & b & a & a \tabularnewline
\hline
a & b & a & a & b \tabularnewline
\hline
a & b & a & b & a \tabularnewline
\hline
\end{tabular}
\hfill
\begin{tabular}{|D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}|}
\hline
 & \# &  & \# &  & \# &  & \# &  & \# & \tabularnewline
\# & \boxed{a} & $\circ$ & \boxed{b} & $\circ$ & \boxed{a} & $\circ$ & \boxed{a} & $\circ$ & \boxed{b} & \# \tabularnewline
 & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ & \tabularnewline
\# & \boxed{b} & $\times$ & \boxed{} &  & \boxed{} &  & \boxed{} &  & \boxed{} & \# \tabularnewline 
 & $\circ$ &  & $\circ$ &  &  &  &  &  &  & \tabularnewline
\# & \boxed{a} & $\circ$ & \boxed{a} & $\times$ & \boxed{} &  & \boxed{} &  & \boxed{} & \# \tabularnewline 
 & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ & \tabularnewline
\# & \boxed{a} & $\circ$ & \boxed{b} & $\circ$ & \boxed{a} & $\circ$ & \boxed{a} & $\circ$ & \boxed{b} & \# \tabularnewline
 & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ &  & $\circ$ & \tabularnewline
\# & \boxed{a} & $\circ$ & \boxed{b} & $\circ$ & \boxed{a} & $\times$ & \boxed{} &  & \boxed{} & \# \tabularnewline
 & \# &  & \# &  & \# &  & \# &  & \# & \tabularnewline
\hline
\end{tabular}
\end{center}
This model is too powerful because it allows cyclic computations which cannot be
removed. In~\cite{lonati2011towards} it will be shown that the language
$L_{a^nb^n}$, the language of all pictures where the first row is equal to
$a^nb^n$, is recognizable by a 2D free automaton, but is not in REC thus the
class of all languages that are accepted by 2D free automaton is not in REC.
This is the reason that in the next chapter we present another automaton model
which was also introduced in~\cite{lonati2011towards}.